package java_thread.update;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 并发搬箱子谜题解答器
 * 摘自https://blog.csdn.net/ahaha413525642/article/details/76945562
 *
 * 进行一定测试，发现效率不是很好，有待优化，但是可以练习并发的处理
 *
 * -- 个人优化版
 */

public class demo_15_ThreadPoolExecutor {
    public static void main(String[] arge) throws InterruptedException{
        // 定义谜题
        Puzzle<Point, Point> puzzle = new Puzzle<Point, Point>() {
            @Override
            public Point initialPosition() {
                return new Point(0,0);  // 起点
            }
            @Override
            public boolean isGoal(Point position) {
                if(position.x.intValue() == 4 && position.y.intValue() == 4 ){ // 终点
                    return true;
                }
                return false;
            }

            @Override
            public Set<Point> legalMoves(Point position) {
                Set<Point> ret =  new HashSet<Point>();
                if (position.getY() > 0){
                    ret.add(new Point(0,-1));
                }
                if (position.getX() > 0){
                    ret.add(new Point(-1,0));
                }
                if (position.getY() < 3){
                    ret.add(new Point(0,+1));
                }
                if (position.getY() < 3){
                    ret.add(new Point(+1,0));
                }
                return ret;  // 移动路径
            }

            @Override
            public Point move(Point position, Point move) {  //移动方法
                Point newPoiot = position.move(move);
//                System.out.println(position.toString() + "->" + newPoiot.toString());
                return newPoiot;
            }
        };
        // 执行谜题解答器
        PuzzleSolver puzzleSolver = new PuzzleSolver(puzzle);
        List<Point> list = puzzleSolver.solve();
        if(null == list){
            System.out.print("未找到对应点");
            return ;
        }
        // 显示路径
        Point point = puzzle.initialPosition();
        for(Point movePoint : list){
            point = point.move(movePoint);
            if(movePoint != list.get(0)){
                System.out.print("->");
            }
            System.out.print(point.toString());
        }
    }
}


//  表示“搬箱子”之类谜题的抽象类(P是点类型，M是路径类型)
interface Puzzle <P, M> {
    P initialPosition();            //设置初始位置
    boolean isGoal(P position);    //判断是否目标位置
    Set<M> legalMoves(P position);  //判断是否有效移动的规则集
    P move(P position, M move);     //移动位置
}

// 位置类(xy表示位置)
class Point {
    Integer x;

    public Point(Integer x, Integer y) {
        this.x = x;
        this.y = y;
    }
    public Point move(Point point){
        return new Point(getX() + point.getX(),getY() + point.getY());
    }

    Integer y;
    public Integer getX() {
        return x;
    }
    public void setX(Integer x) {
        this.x = x;
    }
    public Integer getY() {
        return y;
    }
    public void setY(Integer y) {
        this.y = y;
    }
    @Override
    public String toString() {
        return "{"+x+","+y+"}";
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Point point = (Point) o;

        if (x != null ? !x.equals(point.x) : point.x != null) return false;
        return y != null ? y.equals(point.y) : point.y == null;
    }
    @Override
    public int hashCode() {
        int result = x != null ? x.hashCode() : 0;
        result = 31 * result + (y != null ? y.hashCode() : 0);
        return result;
    }
}

// 用于谜题解决框架的链表节点
class PuzzleNode<P, M> {
    final P pos;   //当前位置
    final M move;  //记录了前一个Node到这个Node的移动
    final PuzzleNode<P, M> prev;   //前一个Node

    PuzzleNode(P pos, M move, PuzzleNode<P, M> prev) {
        this.pos=pos;
        this.move=move;
        this.prev=prev;
    }
    List<M> asMoveList() {    //回溯链接
        List<M> solution = new LinkedList<M>();
        for (PuzzleNode<P, M> n = this; n.move != null; n = n.prev)
            solution.add(0, n.move);
        return solution;
    }
    // 判断
    boolean isHistoryNode(P node){
        for (PuzzleNode<P, M> n = this; n.move != null; n = n.prev){
            if(n.pos.equals(node)) return true;
        }
        return false;
    }
}

//  串行的谜题解答器(略)
class SequentialPuzzleSolver<P,M> {
    private final Puzzle<P,M> puzzle;
    private final Set<P> seen=new HashSet<P>();  //已遍历位置的集合

    public SequentialPuzzleSolver(Puzzle<P,M> puzzle){
        this.puzzle=puzzle;
    }

    public List<M> solve(){
        P pos=puzzle.initialPosition();                      //设置初始位置
        return search(new PuzzleNode<P,M>(pos,null,null));   //返回回溯后的路径
    }

    private List<M> search(PuzzleNode<P,M> node){
        if(!seen.contains(node.pos)){                //如果没走过则加入，走过则返回null
            seen.add(node.pos);
            if(puzzle.isGoal(node.pos))
                return node.asMoveList();             //如果是目标位置，则返回路径
            for(M move:puzzle.legalMoves(node.pos)){  //legalMoves是存放该位置所有有效的移动
                P pos=puzzle.move(node.pos, move);    //pos记录移动后的位置
                PuzzleNode<P,M> child=new PuzzleNode<P,M>(pos,move,node);
                List<M> result=search(child);         //深度优先算法--递归
                if(result!=null)
                    return result;      //只要不是找到目标位置都返回null
            }
        }
        return null;
    }
}

//  并发的谜题解答题
class ConcurrentPuzzleSolver <P, M> {
    private final Puzzle<P, M> puzzle;
    private final ExecutorService exec;
//    private final ConcurrentMap<P, Boolean> seen; // 用线程安全的Map来记录该点是否被遍历过  每个线程各自保存，而每步一个线程，导致数量超大

    // ValueLatch中使用CountDownLatch来实现所需的闭锁行为，并且使用锁定机制来确保解答只会被设置一次
    // 设置为protected，这样包中其他类才能调用
    protected final ValueLatch<PuzzleNode<P, M>> solution = new ValueLatch<PuzzleNode<P, M>>();

    public ConcurrentPuzzleSolver(Puzzle<P, M> puzzle) {
        this.puzzle = puzzle;
        this.exec = initThreadPool();                        // 线程池创建
//        this.seen = new ConcurrentHashMap<P, Boolean>();
        /*
         * 要避免处理RejectedExecutionException，需要将拒绝处理器设置为“抛弃已提交的任务”。
         * 然后，所有未完成的任务最终将执行完成，并且在执行任何新任务时都会失败，从而使Executor结束。
         * （如果任务运行的时间过长，那么可以中断它们而不是等它们完成）。
         */
        if (exec instanceof ThreadPoolExecutor) {
            ThreadPoolExecutor tpe = (ThreadPoolExecutor) exec;
            tpe.setRejectedExecutionHandler(new ThreadPoolExecutor.DiscardPolicy());//当新提交的任务无法保存到队列中等待执行时，DiscardPolicy会悄悄抛弃该任务。
        }
    }

    private ExecutorService initThreadPool() {
//        return Executors.newCachedThreadPool();
        return Executors.newFixedThreadPool(10); // 限制线程
    }

    // 可执行内容，解谜并取得结果
    public List<M> solve() throws InterruptedException {
        try {
            P p = puzzle.initialPosition();
            exec.execute(newTask(p, null, null));
            //阻塞直到找到第一个解答,阻塞方法在闭锁solution中,在此之前，主线程需要等待，ValueLatch提供了一种方式来保存这个值，只有第一次调用才会设置它。
            //在第一次调用setValue时，将更新解答方案，并且CountDownLatch会递减，从getValue中释放主线程。于是开始执行下面
            PuzzleNode<P, M> solnPuzzleNode = solution.getValue();
            return (solnPuzzleNode == null) ? null : solnPuzzleNode.asMoveList();  //返回解答方案的路径
        } finally {
            exec.shutdown();       //第一个找到解答的线程还会关闭Executor，从而阻止接受新的任务。
        }
    }

    protected Runnable newTask(P p, M m, PuzzleNode<P, M> n) {
        return new SolverTask(p, m, n);
    }

    // **重点:计算规则**
    protected class SolverTask implements Runnable {   //继承了Puzzle实现了Runnable
        PuzzleNode<P, M> puzzleNode;
        SolverTask(P pos, M move, PuzzleNode<P, M> prev) {
            puzzleNode = new PuzzleNode(pos, move, prev);    //调用PuzzleNode 的构造函数
        }
        /*
         * 首先计算下一步可能到达的所有位置，并去掉已经到达的所有位置，
         * 然后判断（这个任务或者其他某个任务）是否已经成功地完成，最后将尚未搜索过的位置提交给Executor。
         */
        public void run() {
            //每个任务首先查询solution闭锁，找到一个解答就停止。
            if (solution.isSet()
                    ||  puzzleNode.isHistoryNode(puzzleNode.pos)){         //已经找到了解答或者已经遍历了这个位置
                return; // already solved or seen this position
            }
            if (puzzle.isGoal(puzzleNode.pos)) {
                solution.setValue(puzzleNode); //在第一次调用setValue时，将更新解答方案，并且CountDownLatch会递减，从getValue中释放主线程。
            }else{
                for (M m : puzzle.legalMoves(puzzleNode.pos))
                    //将任务提交到工作者线程中
                    exec.execute(newTask(puzzle.move(puzzleNode.pos, m), m, puzzleNode));
            }
        }
    }
}

// 由ConcurrentPuzzleSolver使用的携带结果的闭锁
// 简单的说，被此类包裹的对象，在第一次get之后阻塞，一直等到第一次set之后才继续执行
class ValueLatch<T>{
    private T value=null;
    //CountDownLatch（倒计时闭锁）是一种灵活的闭锁实现。它可以使一个或多个线程在等待一组事件发生。闭锁状态包括一个计数器，该计数器被初始化为一个正数，表示需要等待的事件数量。
    private final CountDownLatch done=new CountDownLatch(1);   //这里表示只要解答出现一个即可

    public boolean isSet(){      //如果得到了则返回true，否则false
        return (done.getCount()==0);
    }
    public synchronized void setValue(T newValue){
        if(!isSet()){
            value=newValue;
            done.countDown(); //递减
        }
    }
    public T getValue() throws InterruptedException{
        done.await();  //当闭锁值为0是才能执行，之前一直阻塞
        synchronized (this) {
            return value;
        }
    }
}

// 并发谜题解答器扩展--处理在解决器中找不到解答的情况
class PuzzleSolver<P,M> extends ConcurrentPuzzleSolver<P, M> {
    private final AtomicInteger taskCount=new AtomicInteger(0);

    PuzzleSolver(Puzzle<P, M> puzzle){
        super(puzzle);
    }// 调用父类构造

    protected Runnable newTask(P p, M m, PuzzleNode<P,M> n){
        return new CountingSolverTask(p,m,n);
    }
    class CountingSolverTask extends SolverTask{
        CountingSolverTask(P pos, M move, PuzzleNode<P,M> prev) {
            super(pos,move,prev);
            taskCount.incrementAndGet();    //开始一个任务递增
        }
        public void run(){
            try{
                super.run();
            }finally{
                if(taskCount.decrementAndGet()==0)   //结束一个任务递减，最后值为0则解答为null
                    solution.setValue(null);
            }
        }
    }
}